package 简单.位运算;

/**
 * 给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，
 * 统计并返回 计算置位位数为质数 的整数个数。
 * 计算置位位数 就是二进制表示中 1 的个数。
 * 例如， 21 的二进制表示 10101 有 3 个计算置位。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation
 */
public class 二进制表示中质数个计算置位_762 {

    public static void main(String[] args) {

        System.out.println(countPrimeSetBits(842, 888));

    }

    /**
     * 最多有32个1，直接得出，1-32中的质数
     * 2,3,5,11,13,17,19,23,29,31
     *
     * @param left
     * @param right
     * @return
     */
    public static int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int cur = left; cur <= right; cur++) {
            if (isPrime(Integer.bitCount(cur))) {
                ans++;
            }
        }
        return ans;
    }

    public static boolean isPrime(int num) {
        if (num == 2 || num == 3 || num == 5 || num == 7
                || num == 11 || num == 13 || num == 17 || num == 19
                || num == 23 || num == 29 || num == 31) {
            return true;
        }
        return false;
    }

    /**
     * 判断质数优化，位运算巧妙运用
     * 因为 right<= 10 的6次方 < 2的20次方，所以质数在2,3,5,11,13,17,19中
     * 用一个 10100010100010101100=665772 二进制位来表示
     * 求出数字1的个数c，向左移c个位，例如c==2，那么  二进制 2 0 0
     * 和665772进行与位运算，如果不等于0，那么说明是质数
     *
     * @param left
     * @param right
     * @return
     */
    public static int countPrimeSetBits2(int left, int right) {
        int ans = 0;
        for (int cur = left; cur <= right; cur++) {
            if ((1 << Integer.bitCount(cur) & 665772) != 0) {
                ans++;
            }
        }
        return ans;
    }

}
